package dongtai;

public class jiusanyi {
    public static int minFallingPathSum(int[][] matrix) {
        int n=matrix.length;
        if(n==1){
            return matrix[0][0];
        }
        int[][] dp=new int[n+1][n+2];
        dp[n-1][0]=dp[n-2][0]=101;
        dp[n-1][n+1]=dp[n-2][n+1]=101;
        int ret=Integer.MAX_VALUE; ;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i-1][j-1];
            }
            //错误的地方，检查最后一行错误，最后一行并不一定只有三个。只是我分析的时候有三个而已
            if(i==n){
                for(int j=1;j<=n;j++){
                    ret=Math.min(ret,dp[n][j]);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        int i = minFallingPathSum(matrix);
        System.out.println(i);

    }
}
